#ifndef _AMERICO_HEAP_H_
#define _AMERICO_HEAP_H_

#ifdef false
#include <iostream>
#define HeapDebugPrint() Print()
#define HeapDebug(x) std::cout << x
#define HeapDebugLn(x) std::cout << x << std::endl
#else
#define HeapDebugPrint()
#define HeapDebug(x)
#define HeapDebugLn(x)
#endif // _DEBUG

#include <vector>
#include "growingarray.h"

template <typename T>
class Heap
{
public:
	Heap();
	Heap(const std::vector<T> &aVector);
	~Heap();

	void Enqueue(T aValue);
	T Dequeue();
	bool Dequeue(T &aValue);

	bool Head(T &aValue);

	inline unsigned int Size() const;
	void FloydAlgorithm();

	void Clear();

private:
	Utils::GrowingArray<T> myData;

	void Init();
	void BubbleUp(const unsigned int &aPosition);
	void BubbleDown(const unsigned int &aPosition);
	inline void Swap(T &aValue1, T &aValue2);

#ifdef _DEBUG
	void Print();
#endif // _DEBUG
};

template <typename T>
Heap<T>::Heap()
{
	Init();
}

template <typename T>
Heap<T>::Heap(const std::vector<T> &aVector)
{
	myData.Init(aVector.size(), static_cast<unsigned short>(aVector.size()*0.5));
	for(unsigned int index=0; index<aVector.size(); ++index)
	{
		myData.Add(aVector[index]);
	}
	FloydAlgorithm();
}

template <typename T>
Heap<T>::~Heap()
{
	myData.RemoveAll();
}

template <typename T>
void Heap<T>::Enqueue(T aValue)
{
	myData.Add(aValue);
	HeapDebugLn("Enqueue " << aValue);
	BubbleUp(myData.Count()-1);
}

template <typename T>
T Heap<T>::Dequeue()
{
	unsigned int index = myData.Count() - 1;
	if(index<myData.Count())
	{
		T value = myData[0];
		myData[0] = myData[index];
		myData.RemoveCyclicAtIndex(index);
		HeapDebugLn("Dequeue " << value);
		BubbleDown(0);

		return value;
	}
	return 0;
}

template <typename T>
bool Heap<T>::Dequeue(T &aValue)
{
	if(myData.Count())
	{
		aValue = Dequeue();
		return true;
	}
	return false;
}

template <typename T>
bool Heap<T>::Head(T &aValue)
{
	if(myData.Count())
	{
		aValue = myData[0];
		return true;
	}
	return false;
}

template <typename T>
unsigned int Heap<T>::Size() const
{
	return myData.Count();
}

template <typename T>
void Heap<T>::Clear()
{
	myData.RemoveAll();
}

template <typename T>
void Heap<T>::Init()
{
	myData.Init(20,10);
}

template <typename T>
void Heap<T>::BubbleUp(const unsigned int &aPosition)
{
	HeapDebugPrint();
	for(unsigned int index=aPosition; index>0; index = static_cast<unsigned int>((index-1)*0.5))
	{
		unsigned int parent = static_cast<unsigned int>((index-1)*0.5);
		if(myData[index]<myData[parent])
		{
			break;
		}
		Swap(myData[parent], myData[index]);
		HeapDebugPrint();
	}
}

template <typename T>
void Heap<T>::BubbleDown(const unsigned int &aPosition)
{
	if(aPosition<myData.Count())
	{
		HeapDebugPrint();
		unsigned int index = aPosition;
		unsigned int testIndex = 2 * aPosition + 1;
		T value(myData[aPosition]);
		if((testIndex<myData.Count()) && (value < myData[testIndex]))
		{
			index = testIndex;
			value = myData[testIndex];
		}
		if((testIndex+1<myData.Count()) && (value < myData[testIndex+1]))
		{
			index = testIndex+1;
		}
		if(index != aPosition)
		{
			Swap(myData[aPosition], myData[index]);
			BubbleDown(index);
		}
	}
}

template <typename T>
void Heap<T>::FloydAlgorithm()
{
	int nonLeafLevel = static_cast<int>((myData.Count()-1)*0.5);
	HeapDebugPrint();
	for(int index=nonLeafLevel; index>=0; --index)
	{
		HeapDebugLn("Position " << index);
		BubbleDown(index);
	}
}

template <typename T>
void Heap<T>::Swap(T &aValue1, T &aValue2)
{
	T tempValue(aValue1);
	aValue1 = aValue2;
	aValue2 = tempValue;
}

#ifdef _DEBUG
template <typename T>
void Heap<T>::Print()
{
	for(unsigned int index=0; index<myData.Count(); ++index)
	{
		std::cout << "  " << myData[index];
	}
	std::cout << std::endl;
}
#endif // _DEBUG

#endif
